//
// Created by Semir on 2020/5/11.
//

#include <iostream>

using namespace std;

bool matchCore(char* str, char* pattern) {
    if (*str == '\0' && *pattern == '\0') {
        return true;
    }
    if (*str != '\0' && *pattern == '\0') {
        return false;
    }
    if (*(pattern + 1) == '*') {
        if (*str == *pattern) {
            return matchCore(str + 1, pattern) || matchCore(str + 1, pattern + 2) || matchCore(str, pattern + 2);
        } else if (*pattern == '.') {
            if (*str == '\0') {
                return *(pattern + 2) == '\0';
            } else {
                return matchCore(str + 1, pattern) || matchCore(str + 1, pattern + 2) || matchCore(str, pattern + 2);
            }
        } else {
            return matchCore(str, pattern + 2);
        }
    }

    if (*str == *pattern || (*pattern == '.' && *str != '\0')) {
        return matchCore(str + 1, pattern + 1);
    }
    return false;
}

bool match(char* str, char* pattern) {
    if (str == nullptr || pattern == nullptr) {
        return false;
    }
    return matchCore(str, pattern);
}

int main() {
    bool res = match((char*) "bcbbabab", (char*) ".*a*a");
    cout << res << endl;
    return 0;
}
